package algorithm.DivideConquer;

import java.io.*;
import java.util.stream.Stream;

/**
 * 即小和问题
 * 对数组每一个元素，求其左边所有小于等于它的数的总和
 * 然后将所有这些总和加起来，就得到小和
 */
public class SumOfLessThan {

    public static int MAX = 501;
    public static int[] arr = new int[MAX];
    public static int n;
    public static int[] help = new int[MAX];

    //仍然使用ACM输入输出格式
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));

        in.nextToken();
        n = (int) in.nval;
        for (int i = 0; i < n; i++) {
            in.nextToken();
            arr[i] = (int) in.nval;
        }
//        int sum=bruteSumLessThan();
        int sum = sumLessThan(0, n - 1);
        out.print(sum);

        out.flush();
        out.close();
        br.close();

    }

    /**
     * 很容易想到暴力方法
     * 即对每个元素遍历得到小于等于它的和，然后相加
     * 时间复杂度容易分析得O(n^2)
     */
    public static int bruteSumLessThan() {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] <= arr[i]) sum += arr[j];
            }
        }
        return sum;
    }

    /**
     * 使用分治归并的方法实现小和问题
     *
     * @return
     */
    public static int sumLessThan(int l, int r) {
        if (l == r) return 0;
        int m = (l + r) / 2;
        return sumLessThan(l, m) + sumLessThan(m + 1, r) + merge(l, r, m);
    }

    public static int merge(int l, int r, int m) {
        int ans = 0;
        for (int j = m + 1, i = l, sum = 0; j <= r; j++) {
            while (i <= m && arr[i] <= arr[j]) {
                sum += arr[i++];
            }
            ans += sum;
        }
        int i = l;
        int a = l;
        int b = m + 1;
        while (a <= m && b <= r) {
            help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
        }
        while (a <= m) {
            help[i++] = arr[a++];
        }
        while (b <= r) {
            help[i++] = arr[b++];
        }
        for (i = l; i <= r; i++) {
            arr[i] = help[i];
        }
        return ans;
    }
}
